/*
 * @lc app=leetcode.cn id=160 lang=javascript
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 * - 寻找相交节点，意味着两个链表一定有相同的节点
 * - 所以可以通过遍历其中一个链表，并用map结构将链表结点保存成map的key，然后遍历另一条链表，判断map结构中的key是否包含该链表的某个结点，如果包含则直接返回该结点即可
 */
var getIntersectionNode = function(headA, headB) {
    // if(!headA || !headB) return null;
    let pa = headA;
    let pb = headB;
    let map = new Map();
    while(pa) {
        map.set(pa,1);
        pa = pa.next;
    }    
    while(pb) {
        if(map.has(pb)) {
            return pb;
        }
        pb = pb.next;
    }
};

/**
 * 
 * - 因为两个链表的长度不确定，所以需要想办法构造出两个链表长度相同的点；
 * - 假如两个链表拼接起来，则长度都为a+b+2c，距离第一个共同结点的距离都是a+c+b
 */
var getIntersectionNode1 = function(headA, headB) {
    let pa = headA;
    let pb = headB;
    while(pa !== pb) {
        if(pa == null) {
            pa = headB;
        } else {
            pa = pa.next;
        }

        if(pb == null) {
            pb = headA;
        } else {
            pb = pb.next;
        }
    }
    return pa;
}
// @lc code=end

